1. Field of the Invention
This invention relates generally to computer program compiling, and more specifically to range check elimination optimization in a dynamic compiling environment.
2. Description of the Related Art
Currently, many computer programs exist as compiled object code, which is designed to operate only on one particular operating system. In an effort to increase the efficiency associated with the execution of such computer programs, optimized compiling has been implemented. Optimizing a computer program generally attempts to eliminate portions of the computer code, which are essentially unused. In addition, optimizing may include performing program transformations to allow overall computations to be performed more efficiently, thereby consuming fewer computer resources. One such program transformation is range check elimination.
By way of background, many Java applications utilize arrays, which are an arrangement of information in one or more dimensions, e.g., a list, a table, or a multidimensional arrangement of data. Whenever an array is realized in memory using Java the size of the array is stored in memory along with any data referenced by the array. Generally, the Java array size is stored before the first element in the array.
For example, a one hundred element array in Java will have the number one hundred stored before the first element of the array. Thus, in order to keep the required number of elements free for data storage, arrays in Java are typically larger than would otherwise need to be in order to store a particular number of elements.
As instructions are interpreted by a Java Virtual Machine (JVM), one the operations that must be performed by the interpreter is an array boundary check. Specifically, whenever a Java array is accessed by a Java application, an array boundary check must be performed to ensure that before the array is accessed the element attempting to be accessed is not outside the boundary of the array. When an array access command attempts to access an element outside the boundary of the array an exception is triggered. Generally, the raised exceptions are configured to prevent memory access when they are raised.
Array boundary checking results in a more robust system since array access commands have access only to those data elements defined by the array, and no access to adjacent data is possible, resulting in fewer bugs and improved system security. However, the step-by-step comparison and verification required for array boundary checking, which typically requires several CPU cycles per check, consume valuable processing time.
Since JVMs have conventionally been implemented in software, boundary checking in Java is typically a process that adds extra machine cycles every time an array is accessed. The extra machine cycles utilized for array boundary checking greatly reduce the operating efficiency of the system, which only serves to further exacerbate an already slow, software-based, interpretive process.
Range check elimination attempts to optimize loop structures by removing array boundary checks from the main loop structure. To do this, conventional compilers attempt to prove a property over the entire loop structure that proves the array boundary check will pass before the loop structure is even entered. Thus, conventional compilers typically generate a test before the loop, then, after the test is passed, the main loop body can be entered.
For example if a loop structure is a “For” loop structure that indexes an array, conventional compilers will compare the loop limit variable to the array length prior to entering the loop structure. If the loop limit variable is larger than the array length, the program will take some other path. Otherwise, the compiler knows the array indexing variable will not be larger than the array length, and thus, the loop can be executed without further array boundary checks.
Thus, conventional compilers discover all the array access operations within a loop structure and attempt to relate the array indexes from those instructions to the length of the loop. The compilers then attempt to create a test prior to entering the loop that ensures all the array access operations in the loop will not violate the array boundary limits.
Unfortunately, when loops include array access operations that only occur when a particular condition is TRUE, conventional compilers generally cannot determine accurately whether the array boundaries will be violated. For example, an array can be accessed using the loop variable plus an offset if a particular condition is true. In this example, the array boundary check would only cause an exception if the loop variable is sufficiently high and the particular condition is TRUE.
Thus, during the above conditions, conventional compilers cannot relate the faulting array access to the condition being FALSE. Under these circumstances conventional compilers operate conservatively and leave the array boundary check within the loop structure.
In view of the foregoing, there is a need for systems and methods that speed up loop intensive programs in a dynamic compiling environment. The methods should provide efficient range check elimination in a dynamic compiling environment, such as in a Java virtual machine. To this end, the systems and methods should be capable of performing range check elimination acceptably fast to allow optimization to occur in a dynamic environment without unacceptable slowing of the compiling process.